﻿using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Text;
using System.Windows.Forms;
using System.IO;


namespace Grafos
{

    public partial class Form1 : Form
    {

        private Dictionary<Node, List<Node>> _listaAdj = new Dictionary<Node, List<Node>>();

        private int _contBuscarArt = 0;

        private Queue<Node> _queue = new Queue<Node>();

        public Form1()
        {
            InitializeComponent();
            txtPath.Focus();
        }

        private void btnGerarLista_Click(object sender, EventArgs e)
        {

            string path = txtPath.Text.Trim();
            int rm = int.Parse(txtRM.Text.Trim());
            int niveis = int.Parse(txtLevels.Text.Trim());

            if (!string.IsNullOrWhiteSpace(path) )
            {
                Dictionary<int, List<int>> lista = null;

                try
                {
                    lista = lerArquivo(path);
                }
                catch (IOException)
                {
                    MessageBox.Show("O texto informado não é um caminho" +
                        " válido.");

                    txtPath.Clear();
                    txtPath.Focus();
                }

                validarEntrada(lista);

                montarListaAdj(lista);

                btnGo.Enabled = false;

                imprimirListaAdj();

                Node eu = retornaNo(rm);

                buscarArt(eu);

                listarArticulacoes();

                TraversalLargura(eu);

                int contatos = contarContatos(niveis);

                lblNiveis.Text = contatos.ToString();

                List<Node> folhas = buscarFolhas(eu);

                List<Stack<Node>> stacks = verificarCaminhos(folhas);

                imprimirCaminhos(stacks);

                imprimirUnreachable(eu);

            }
            else
            {
                MessageBox.Show("Informe o caminho da pasta.");
            }
        }

        private bool validarEntrada(Dictionary<int, List<int>> lista)
        {
            var valido = true;
            HashSet<int> adjs = new HashSet<int>();

            foreach (var kvp in lista)
            {
                foreach (var rm in kvp.Value)
                {
                    adjs.Add(rm);
                }
            }

            List<int> keys = new List<int>();

            foreach (var rm in lista.Keys)
            {
                keys.Add(rm);
            }


            foreach (var rm in adjs)
            {
                if (!keys.Contains(rm))
                {
                    MessageBox.Show("O arquivo de entrada não é valido. O rm " + 
                        rm + " é adjacente mas nao é o nome de nenhum arquivo.");
                    valido = false;
                    break;
                }

               
            }

            return valido;
        }


        private void imprimirCaminhos(List<Stack<Node>> stacks)
        {
            string str = string.Empty;

            foreach (var stack in stacks)
            {
                while (!(stack.Count == 0))
                {
                    Node no = stack.Pop();
                    str += no.Value + "; ";
                }

                str += "\n";
            }

            lblCaminhos.Text = str;
        }

        private List<Stack<Node>> verificarCaminhos(List<Node> folhas)
        {
            List<Stack<Node>> stacks = new List<Stack<Node>>();

            foreach (var folha in folhas)
            {
                Stack<Node> stack = new Stack<Node>();

                stack.Push(folha);

                Node pai = folha.Pai;

                while(pai != null)
                {
                    stack.Push(pai);
                    pai = pai.Pai;              
                }

                stacks.Add(stack);
            }

            return stacks;
        }

        private void imprimirUnreachable(Node eu)
        {
            foreach (var no in _listaAdj.Keys)
            {
                if (!canReach(no,eu) && !no.Equals(eu))
                {
                    lblUnreachable.Text += no.Value + "; ";
                }
                
            }
        }


        private bool canReach(Node origem, Node alvo)
        {
            bool can = false;

            Node pai = origem.Pai;

            while (pai != null)
            {
                if (pai.Equals(alvo))
                {
                    can = true;
                    break;
                }
                else
                {
                    pai = pai.Pai;
                }
            }

            return can;

        }

        private List<Node> buscarFolhas(Node eu)
        {
            List<Node> folhas = new List<Node>();

            foreach (var no in _listaAdj.Keys)
            {
                if (!isFather(no))
                {
                    if (canReach(no, eu))
                    {
                        folhas.Add(no);
                    }
                }
                    
            }

            return folhas;
        }

        private bool isFather(Node no)
        {
            bool isFather = false;

            foreach (var node in _listaAdj.Keys)
            {
                if (node.Pai != null)
                {
                    if (node.Pai.Equals(no))
                    {
                        isFather = true;
                        break;
                    }
                }
            }

            return isFather;

        }


        private int contarContatos(int niveis)
        {
            int contatos = 0;

            foreach (var no in _listaAdj.Keys)
            {
                if (no.Prof <= niveis && no.Prof != 0)
                    contatos++;
            }

            return contatos;
        }


        private void TraversalLargura(Node raiz)
        {

            raiz.VisitedLarg = true;
            raiz.Prof = 0;
            _queue.Enqueue(raiz);

            while (_queue.Count != 0)
            {
                Node no = _queue.Dequeue();

                foreach (var adj in no.Adjacentes)
                {
                    if (!adj.VisitedLarg)
                    {
                        adj.VisitedLarg = true;
                        adj.Prof = no.Prof + 1;
                        _queue.Enqueue(adj);
                    }
                }
            }
        }


        private void listarArticulacoes()
        {
            string str = null;

            foreach (Node no  in _listaAdj.Keys)
            {
                if (no.Art)
                    str += no.Value + "; ";
                
            }

            if (!string.IsNullOrEmpty(str))
                lblArt.Text = str;
            else
                lblArt.Text = "Sem articulações";
            
        }



        private void montarListaAdj(Dictionary<int, List<int>> lista)
        {
            foreach (var vp in lista)
            {
                Node no = retornaNo(vp.Key);
                List<Node> adjacentes = new List<Node>();

                if (no == null)
                {
                    no = new Node();
                    no.Value = vp.Key;

                }

                foreach (var rm in vp.Value)
                {
                    Node n = retornaNo(rm);

                    if (n == null)
                    {
                        n = new Node();
                        n.Value = rm;

                    }

                    adjacentes.Add(n);
                    no.Adjacentes.Add(n);
                }

                _listaAdj.Add(no, adjacentes);

            }

        }


        private Node retornaNo(int rm)
        {
            foreach (var kvp in _listaAdj)
            {
                if (kvp.Key.Value == rm)
                    return kvp.Key;

                foreach (var node in kvp.Value)
                {
                    if (node.Value == rm)
                        return node;
                }
            }

            return null;
        }


        private void imprimirListaAdj()
        {
            string temp = null;

            foreach (KeyValuePair<Node, List<Node>> vp in _listaAdj)
            {
                temp += vp.Key.Value + " -- > ";

                foreach (Node n in vp.Value)
                {
                    temp += n.Value + ", ";
                }

                temp += "\n";
            }

            lblAdj.Text = temp;
        }


        private Dictionary<int, List<int>> lerArquivo(string path)
        {
            Dictionary<int, List<int>> lista = new Dictionary<int, List<int>>();

            foreach (string file in Directory.GetFiles(path))
            {
                string valor = Path.GetFileNameWithoutExtension(file);
                string[] adj = null;
                string str;

                using (StreamReader sr = new StreamReader(file))
                {
                    str = sr.ReadToEnd();
                }

                if (!string.IsNullOrWhiteSpace(str))
                {
                    adj = str.Split(',');
                }
                
                lista.Add(toInt(valor), toInt(adj));

            }

            return lista;

        }

        private List<int> toInt(string[] adj)
        {
            List<int> lista = new List<int>();

            if (!(adj == null))
            {
                foreach (string val in adj)
                {

                    int temp = toInt(val);
                    lista.Add(temp);
                }
            }
            return lista;
        }

        private int toInt(string valor)
        {
            valor.Trim();

            if (valor.StartsWith("rm", true, null))
            {
                valor = valor.Remove(0, 2);
            }

            return int.Parse(valor);
        }



        public void buscarArt(Node v)
        {
            v.VisitedProf = true;
            v.Low = v.Num = ++_contBuscarArt;

            foreach (var w in v.Adjacentes)
	        {
		        if(!w.VisitedProf)
                {
                    w.Pai = v;
                    buscarArt(w);

                    if (w.Low >= v.Num)
                    {
                        v.Art = true;
                    }

                    v.Low = min(v.Low, w.Low);
                }
                else
                {
                    if(!w.Equals(v.Pai))
                    {
                        v.Low = min(v.Low, w.Num);
                    }
                }
	        }
            
        
        }

        private int min(int p1, int p2)
        {
            if (p1 >= p2) return p2;
            else return p1;
        }

        private void lblCaminhos_Click(object sender, EventArgs e)
        {

        }
    }

    public class Node
    {

        private int _value;

        public int Value
        {
            get { return _value; }
            set { _value = value; }
        }

        private Node _pai = null;

        public Node Pai
        {
            get { return _pai; }
            set { _pai = value; }
        }

        private bool _visitedProf = false;

        public bool VisitedProf
        {
            get { return _visitedProf; }
            set { _visitedProf = value; }
        }

        private bool _visitedLarg = false;

        public bool VisitedLarg
        {
            get { return _visitedLarg; }
            set { _visitedLarg = value; }
        }
        private bool _art = false;

        public bool Art
        {
            get { return _art; }
            set { _art = value; }
        }

        private int _prof;

        public int Prof
        {
            get { return _prof; }
            set { _prof = value; }
        }

        private int _num;

        public int Num
        {
            get { return _num; }
            set { _num = value; }
        }

        private int _low;

        public int Low
        {
            get { return _low; }
            set { _low = value; }
        }

        private List<Node> _adjacentes = new List<Node>();

        public List<Node> Adjacentes
        {
            get { return _adjacentes; }
            set { _adjacentes = value; }
        }


    }
}
